Compilers are generally used to transform one representation of a computer program into another representation. Typically, but not exclusively, compilers are used to transform a human readable form of a program such as source code into a machine readable form such as object code. By doing so, a human programmer is able to write a computer program in a high level, human readable form, and then generate low level program code that operates quickly and efficiently on a particular type of computer.
One type of compiler is an optimizing compiler, which includes an optimizer or optimizing module for enhancing the performance of the machine readable representation of a program. Some optimizing compilers are separate from a primary compiler, while others are built into a primary compiler to form a multi-pass compiler. Both types of compilers may operate either on a human readable form, a machine readable form, or any intermediate representation between these forms.
Many optimizing modules of compilers operate on intermediate representations of computer programs, and often on specific routines or procedures within those programs. Other optimizers are interprocedural optimizers that are capable of operating upon multiple procedures, or compilation units, collectively.
A wide variety of optimizations may be performed during compilation of a computer program. Some optimizations focus on optimizing the execution of program statements, and in particular expressions that are calculated by those statements. An expression typically incorporates at least one argument and at least one operation, be it logical, arithmetical, etc., to be performed on the argument. Thus, for example, the expression “a+b” has arguments “a” and “b” and an addition operation.
One type of expression-based optimization, for example, is copy propagation, or redundant copy elimination, which is a form of expression reduction that attempts to locate copy expressions and “propagate” the results of such expressions to later expressions that use the results of the earlier expressions. Thus, for example, if an expression “t=s” is followed by the expression “x=t+z”, and it is known that the value of t never changes between the expressions, the first expression can be eliminated, and the second expression can be modified to the de facto equivalent expression “x=s+z”. As such, one expression is eliminated, and the program executes more efficiently as a result.
Another type of expression-based optimization is forward store motion, which attempts to move expressions that are calculated all of the time, but used only some of the time, to locations where they will only be calculated when necessary. Thus, for example, if a particular expression “x=t+z” is found in a program, and is followed by a conditional statement that branches down one of two paths based upon a decision that does not involve the outcome of that expression, and that uses the value of x in only one of those paths, often the expression can be moved to that path so that the expression will not be calculated when the program proceeds along the other path.
Other types of optimizations are based in part on optimizing the execution of routines within a computer program, e.g., various procedures, functions, methods, etc. that perform various desirable operations that need to be accessed at different points in a computer program. Through the use of routines, a sequence of program code that performs a particular operation does not need to be repeated in the program every time that particular operation is desired. Rather, the sequence of program code can be organized into a routine, so that every time that operation is required, a routine call may be made to invoke execution of the routine.
Routines are often capable of receiving input and/or generating output. Input is often received through one or more input parameters supplied within a call to the routine. A routine also is typically defined with a particular “signature” that defines what input parameters are expected when a routine is invoked by a routine call. Thus, whenever it is desirable to invoke a routine, a call is made with the expected input parameters supplied within the call. Thus, for example, if a particular routine is provided to print text to a video display, the routine signature might specify that a text string to be displayed be provided in the routine call. Conventional programming environments often denote routine calls through the use of the name of the routine being called, followed by the input parameters separated by commas and delimited by parentheses. Thus, assuming the aforementioned routine is named “print”, a routine call to that routine might take the form of “print(“Hello World!”)”, where the input parameter is the text string “Hello World!”.
The use of routines can substantially simplify program development, as preexisting routines can often be reused in new computer programs simply by generating suitable routine calls in the new programs. Nonetheless, the invocation of routines often comes with increased processing overhead, and can slow performance. Thus, a number of optimizations focus on avoiding unnecessary routine calls in certain circumstances. As an example, “inlining” is a particular optimization that is sometimes used to replace a call to a particular routine with the actual program code in the body of the routine. Given, however, that inlining typically increases the size of the resulting optimized program code, it is typically limited to those situations where a distinct performance benefit can be obtained.
Despite the performance gains that can be obtained via the aforementioned conventional optimizations, and in particular with respect to optimizing the usage of expressions and routines, a significant need still exists for improved optimization approaches that derive additional performance benefits over those available through conventional approaches.